package sortAlgorithm;

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		int[] a = { 3, 2, 5, 7, 6, 9 };
		quickSort(a);
		System.out.println(Arrays.toString(a));
	}

	public static void quickSort(int[] array) {
		quickSort(array, 0, array.length - 1);
	}
	/**
	 * 快速排序
	 * 从小到大
	 * @param array	待排数组
	 * @param begin	开始元素下标
	 * @param end	结束元素下标
	 */
	private static void quickSort(int[] array, int begin, int end) {
		if (begin < end) {
			int q = partition(array, begin, end);
			quickSort(array, begin, q - 1);
			quickSort(array, q + 1, end);
		}
	}
	/**
	 * 双向扫描分区、三点中值法
	 * @param array	数组
	 * @param begin	开始下标
	 * @param end	结束下标
	 * @return		数组中间分界点下标
	 */
	private static int partition(int[] array, int begin, int end) {
		// 三点中值法：在being、mid、end对应元素中选取中间值作为主元
		int mid = begin + ((end - begin) >> 1);
		int a = array[begin], b = array[end], c = array[mid];
		int midIndex;
		if ((a > b && a < c) || (a > c && a < b)) {
			midIndex = begin;
		} else if ((b > a && b < c) || (b > c && b < a)) {
			midIndex = end;
		} else {
			midIndex = mid;
		}
		// 中值元素与首元素交换
		int swap = array[begin];
		array[begin] = array[midIndex];
		array[midIndex] = swap;
		//双向扫描分区
		int element = array[begin];
		int left = begin + 1, right = end;
		while (left <= right) {
			while (left <= right && array[left] <= element) {
				left++;
			}
			while (left <= right && array[right] > element) {
				right--;
			}
			if (left < right) {
				int temp = array[left];
				array[left] = array[right];
				array[right] = temp;
			}
		}
		array[begin] = array[right];
		array[right] = element;
		return right;
	}

}
